#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "seqlist.h"

int seqlist_init(seqlist_t **mylist, int capacity, int size)
{
    if (NULL != *mylist)
        return -1;

    *mylist = malloc(sizeof(seqlist_t));
    if (NULL == *mylist) // 线性表开辟失败
        return -1;

    (*mylist)->arr = malloc(capacity * size); // 为 arr 分配内存，注意运算符优先级
    if (NULL == (*mylist)->arr) { // 数组开辟失败
        free(*mylist);
        *mylist = NULL;
        return -1;
    }

    (*mylist)->capacity = capacity;
    (*mylist)->nmemb = 0;
    (*mylist)->size = size;
    return 0;
}

// 满
int seqlist_is_full(const seqlist_t *mylist)
{
    return mylist->nmemb == mylist->capacity;
}

// 增
int seqlist_insert(seqlist_t *mylist, const void *data)
{
    char *ptr = NULL;
    if (seqlist_is_full(mylist)) { // 存储满了，需要扩容
        ptr = realloc(mylist->arr, (mylist->capacity + INCREACE_CNT) * mylist->size); // 扩容
        if (NULL == ptr)
            return -1; // 扩容失败
        mylist->arr = ptr; // 扩容成功，改变数组指向
        mylist->capacity += INCREACE_CNT;
    }

    // 添加元素
    memcpy((char *)(mylist->arr) + mylist->nmemb * mylist->size, data, mylist->size);
    mylist->nmemb++;

    return 0;
}

// 找
void *seqlist_find(const seqlist_t *mylist, const void *key, cmp_t cmp)
{
    int i;
    for (i = 0; i < mylist->nmemb; i++) {
        if (0 == cmp(key, (char *)(mylist->arr) + i * mylist->size))
            return (char *)(mylist->arr) + i * mylist->size;
    }

    return NULL;
}

// 删
int seqlist_delete(seqlist_t *mylist, const void *key, cmp_t cmp)
{
    int del_pos;
    void *ptr = seqlist_find(mylist, key, cmp);
    if (NULL == ptr)
        return -1; // 未找到对应元素

    // 删除元素
    del_pos = ((char *)ptr - (char *)(mylist->arr)) / mylist->size; // 要删除的元素的下标
    memcpy(ptr, (char *)ptr + mylist->size, (mylist->nmemb - del_pos - 1) * mylist->size);
    mylist->nmemb--;

    // 缩容列表空间
    if ((mylist->capacity - mylist->nmemb) > INCREACE_CNT) {
        ptr = realloc(mylist->arr, (mylist->capacity - INCREACE_CNT / 2) * mylist->size);
        if (NULL == ptr)
            return -2; // 缩容失败
        mylist->arr = ptr;
        mylist->capacity -= INCREACE_CNT / 2;
    }

    return 0;
}

// 遍历
void seqlist_traval(const seqlist_t *mylist, pri_t pri)
{
    int i;
    for (i = 0; i < mylist->nmemb; i++)
        pri((char *)(mylist->arr) + i * mylist->size);
    printf("\n");
}

// 销毁
void seqlist_destroy(seqlist_t **mylist)
{
    if (NULL == *mylist)
        return;

    // 释放空间
    free((*mylist)->arr);
    (*mylist)->arr = NULL;
    free(*mylist);
    *mylist = NULL;
}

// 插入且有序         
int seqlist_insert_sort(seqlist_t *mylist, const void *data, cmp_t cmp)
{
    char *ptr = NULL;
    int i;
    if (seqlist_is_full(mylist)) { // 存储满了，需要扩容
        ptr = realloc(mylist->arr, (mylist->capacity + INCREACE_CNT) * mylist->size); // 扩容
        if (NULL == ptr)
            return -1; // 扩容失败
        mylist->arr = ptr; // 扩容成功，改变数组指向
        mylist->capacity += INCREACE_CNT;
    }

    // 有序插入
    for (i = 0; i < mylist->nmemb; i++) {
        if (cmp((char *)mylist->arr + i * mylist->size, data) > 0) { // 在下标为i的元素前插入新的元素
            memmove((char *)mylist->arr + (i + 1) * mylist->size, \
                    (char *)mylist->arr + i * mylist->size, \
                    (mylist->nmemb - i) * mylist->size); // 后移元素
            memcpy((char *)mylist->arr + i * mylist->size, data, mylist->size); // 插入元素
            mylist->nmemb++;
            return 0;
        }
    }

    // 如果没有插入，说明元素比所有现有元素都大(或小)，放在末尾
    memcpy((char *)mylist->arr + mylist->nmemb * mylist->size, data, mylist->size);
    mylist->nmemb++; // 增加元素个数
    return 0;
}

